package ch01;

import java.util.HashSet;
import java.util.Set;

/**
 * Implement an algorithm to determine if a string has all unique characters. 
 * What if you cannot use additional data structures?
 * @author Xi Chen
 *
 */

public class IsUnique_01 {
	/**
	 * O(n^2)
	 * @param s
	 * @return
	 */
	public static boolean isUnique(String s) {
		for (int i = 0; i < s.length() - 1; i++) {
			for (int j = i + 1; j < s.length() ; j++) {
				if (s.charAt(i) == s.charAt(j)) {
					return false;
				}
			}
		}
		return true;
	}
	
	/**
	 * O(n)
	 * @param s
	 * @return
	 */
	public static boolean isUnique2(String s) {
		Set<Character> mySet = new HashSet<Character>();
		for (int i = 0; i < s.length(); i++) {
			mySet.add(new Character(s.charAt(i)));
		}
		return (mySet.size() == s.length() ? true : false);
	}

	public static void main(String[] args) {
		String s = "abc123456efghijl m1";
		System.out.println(isUnique(s));
		System.out.println(isUnique2(s));
	}

}
